
rem
	bbdoc: Node for use in a quad-tree Artemax system.
	
	about:
	leaf node = not subdivided, contains entities.
	branch node = subdivided, has children nodes, contains no entities.
	
end rem
Type TQuadTreeNode

	'global fields: mappers for all nodes
	'Set by the system when it is created.
	Global _positionMapper:TComponentMapper
	Global _transformMapper:TComponentMapper
	Global _hitboxMapper:TComponentMapper
	Global _quadTreeMapper:TComponentMapper
			
	'area covered by this node.
	Field _area:TRect
	
	'entities in this node are listed here.	
	'a node with entities is called a leaf node.
	Field _entityList:TList

	'child nodes will go here
	'0 = topleft, 1 = topright, 2 = bottomleft, 3 = bottomright
	'a node with nodes in it is a branch node.
	Field _node:TQuadTreeNode[4]
	
	'bool
	Field _partitioned:Int
	
	'max amount of entities in this node before subdivide
	'and becoming a branch node.
	Field _maxEntities:Int
	
	'reference to this nodes' parent node
	Field _parentNode:TQuadTreeNode
	
	'reference to system this node belongs to.
	'enables this node to call Resize(),
	'to resize the quad-tree area
	Field _system:TQuadTreeSystem
	
	'for debug purposes
	Field _r:Int = 150'Rand(200, 255)
	Field _g:Int = 150'Rand(200, 255)
	Field _b:Int = Rand(200, 255)
	
	
		
	Method New()
		_entityList = New TList
		_area = New TRect
		_partitioned = False
	End Method
	
		
	
	'Constructor.
	Function Create:TQuadTreeNode(x:Int, y:Int, w:Int, h:Int, system:TQuadTreeSystem,  ..
				maxEntities:Int = 50, parentNode:TQuadTreeNode = Null)
		Local n:TQuadTreeNode = New TQuadTreeNode
		n.SetParentNode(parentNode)
		n.SetSystem(system)
		n.SetMaxEntities(maxEntities)
		n.SetArea(x,y, w,h)
		Return n
	End Function
	
	
	'frees node content.
	Method Free()
		_entityList.Clear()
		_entityList = Null
		_area = Null
		
		If _partitioned
			For Local n:Int = 0 To 3
				_node[n].Free()
			Next
			_partitioned = False
		End If
	End Method
	
	
	Method SetArea(x:Int, y:Int, w:Int, h:Int)
		_area.SetPosition(x, y)
		_area.SetDimension(w, h)
	End Method
	
	
	Method GetArea:TRect()
		Return _area
	End Method
	
	
	Method GetEntityList:TList()
		Return _entityList
	End Method

	
	Method SetSystem(s:TQuadTreeSystem)
		_system = s
	End Method
	

	Method SetParentNode(n:TQuadTreeNode)
		_parentNode = n
	End Method
	
	
	Method SetMaxEntities(m:Int)
		_maxEntities = m
	End Method
	
		
	Method Partition()
		If Not _partitioned
			Local childWidth:Int = _area.GetWidth() / 2
			Local childHeight:Int = _area.GetHeight() / 2
			'topleft
			_node[0] = TQuadTreeNode.Create(_area.GetX(), _area.GetY(),  ..
						childWidth, childHeight, _system, _maxEntities, Self)
			'topright
			_node[1] = TQuadTreeNode.Create(_area.GetX() + childWidth, _area.GetY(),  ..
						childWidth, childHeight, _system, _maxEntities, Self)
			'bottomleft
			_node[2] = TQuadTreeNode.Create(_area.GetX(), _area.GetY() + childHeight,  ..
						childWidth, childHeight, _system, _maxEntities, Self)
			'bottomright
			_node[3] = TQuadTreeNode.Create(_area.GetX() + childWidth, _area.GetY() + childHeight,  ..
						childWidth, childHeight, _system, _maxEntities, Self)

			_partitioned = True
						
			'move entities in this node to the new child nodes			
			For Local e:TEntity = EachIn _entityList
				PushEntityDown(e)
			Next
		End If
	End Method
	
	
	'Adds all entities in this node to passed list.	
	'Recursively called when node is partioned.
	'Entities can be in multiple nodes at the same time, so 
	'each entity is only added once.
	Method GetAllEntities(l:TList)

		'add all items in this node to list
		For Local e:TEntity = EachIn _entityList
			If l.Contains(e) Then Continue
			l.AddLast(e)
		Next
		
		'get entities in children
		If _partitioned
			For Local n:Int = 0 To 3
				_node[n].GetAllEntities(l)
			Next
		End If
	End Method
	
	
	'removes passed entity from this node.
	'or sub nodes
	Method RemoveEntity(e:TEntity)

		'remove entity from this node list
		If _entityList.Contains(e) Then _entityList.Remove(e)
		
		'and try sub nodes
		If _partitioned
			For Local n:Int = 0 To 3
				_node[n].RemoveEntity(e)
			Next
		End If
	End Method	

	
	'Adds all entities that overlap passed area to passed bag.
	'Recursively called when node is partioned.
	Method GetEntities(bag:TBag, rect:TRect)
		
		'check if passed rect OVERLAPs this node area.
		If _area.OverLappedBy(rect)
			Local r:TRect
			
			'find all entities in this node that also overlap the passed rect
			For Local e:TEntity = EachIn _entityList
				r = _system.GetEntityRect(e)

				'does this entity rect overlap the passed rect?
				If rect.OverLappedby(r) Then
					bag.Set(e.GetId(), e)
				Else
					bag.Set(e.GetId(), Null)
				EndIf
			Next
			
			'check all subnodes
			If _partitioned
				For Local n:Int = 0 To 3
					_node[n].GetEntities(bag, rect)
				Next
			End If
		End If
	End Method
	
	
	' Inserts an item into this node. Partitions this node when needed.	
	Method InsertEntity(e:TEntity)
		If Not InsertInChild(e)
		
			'not added to child node: add to this node.
			'but only once.
			If _entityList.Contains(e) Then Return
			_entityList.AddLast(e)
			
			Local quadItem:TQuadTreeComponent = TQuadTreeComponent(_quadTreeMapper.Get(e))
			quadItem.SetParentNode(Self)
			
			'need to partition this node?
			If Not _partitioned And _entityList.Count() > _maxEntities
				Partition()
			End If
		EndIf
	End Method
			
		
	'try to insert item into child node.
	'call back to InsertItem() adds recursion.
	'position of entity is used to determine parent node.
	Method InsertInChild:Int(e:TEntity)
	
		'cannot add to branch node
		If Not _partitioned Then Return False

'		Local r:TRect = _system.GetEntityRect(e)		
		Local p:TVector2D = _system.GetEntityPoint(e)

		'add to one of the child nodes
		For Local n:Int = 0 To 3
'			If _node[n].RectInNode(r)
			If _node[n].PointInNode(p)
				_node[n].InsertEntity(e)
				Return True
			End If
		Next
		Return False
	End Method
	

	'Moves entity to a child node.
	Method PushEntityDown:Int(e:TEntity)
		If InsertInChild(e)
			_entityList.Remove(e)
			Return True
		End If
		Return False
	End Method
	
	
	'Moves entity to this node's parent node.
	Method PushEntityUp:Int(e:TEntity)
		_entityList.Remove(e)
		_parentNode.InsertEntity(e)
	End Method
	

	'tries to move item in the tree.
	'called by quadtreesystem.processentity()
	Method MoveEntity(e:TEntity)
		Local r:TRect = _system.GetEntityRect(e)
		If Not PushEntityDown(e)
		
			'child node does not accept this entity,
			'push to parent instead
			If _parentNode
				PushEntityUp(e)
			ElseIf Not _area.Inside(r)
				'we're in root node and entity does not fit :(
				
				'resize world.
				'(the entity is placed as well during that operation)
				_system.Resize(r)
			EndIf
		End If
	End Method	
	
	
	'Returns true if passed rect is INSIDE this node area.
	Method RectInNode:Int(r:TRect)
		Return _area.Inside(r)
	End Method

		
	'Returns true if passed rect overlaps this node area.
	Method RectOverlapsNode:Int(r:TRect)
		Return _area.OverlappedBy(r)
	End Method
	
	
	'Returns true if passed point is inside this node area.
	Method PointInNode:Int(p:TVector2d)
		Return _area.PointInside(p)
	End Method
	
	
	'for debugging purposes
	Method Render()
		DrawLine(_area.GetX(), _area.GetY(), _area.GetX() + _area.GetWidth(), _area.GetY())
		DrawLine(_area.GetX(), _area.GetY() + _area.GetHeight(), _area.GetX() + _area.GetWidth(), _area.GetY() + _area.GetHeight())
		DrawLine(_area.GetX(), _area.GetY(), _area.GetX() , _area.GetY() + _area.GetHeight())
		DrawLine(_area.GetX() + _area.GetWidth(), _area.GetY(), _area.GetX() + _area.GetWidth() , _area.GetY() + _area.GetHeight())
		
		'only show number of entities in a leaf node.
		If Not _partitioned Then DrawText("" + _entityList.Count(), _area.GetX() + 2, _area.GetY() + 2)
		
		If _partitioned
			For Local n:Int = 0 To 3
				_node[n].Render()
			Next
		End If
	End Method
	
End Type